프로그래머스 - 숫자 야구

문제 사이트

https://school.programmers.co.kr/learn/courses/30/lessons/451808

문제 간단 요약

입력

• 최대 제출 횟수(n)
  • submit을 제출할 수 있는 횟수 제한
  • 6 <= n<= 3024
• 숫자 제출 함수(submit)
  • 1000이상 9999이하의 정수를 입력받음
  • “xS yB” 형식의 문자열로 return
    • xS: 스트라이크가 x개 있음
    • yB: 볼이 y개 있음

출력

• submit함수를 n회 초과하지 않은 상태에서 올바른 번호를 return하기

조건

• S: 스크라이크
  • 숫자가 있으며, 올바른 위치에 들어감
• B: 볼
  • 숫자가 있지만, 올바르지 않은 위치에 들어감
• 4자리 숫자의 각 자리 수는 다름

풀이

고려할 점

• 숫자가 중복으로 들어가는 경우의 수 제거
  • set으로 중복 숫자를 제거하여 사용
• 제출 결과를 통해 가능한 후보군을 줄이는 과정 필요
  • compare(a, b): a와 b를 비교했을 때의 결과 반환
• 다음 제출할 최적의 후보군 선택
  • pick(cands): 후보군 중에서 가장 최적의 후보군을 선택하여 반환함
  • Minimax알고리즘 : 최악의 피해를 최소화하는 질문을 선택하는 알고리즘
    • Max: 이 질문에서 가장 나쁜 경우(후보가 가장 많이 남는 경우)
    • Min: 그 가장 나쁜 경우를 가장 작게 만드는 질문을 선택

전체적인 과정

1. 중복 숫자가 있는 4자리 번호는 제거한다.
2. 후보군 중에서 가장 피해가 작은 최적의 후보군을 선택한다.
3. 해당 후보군을 제출하여 실제 결과를 바탕으로 후보군을 필터링한다.
4. 이를 반복하여, 최종 비밀번호를 찾는다.

1. 중복 숫자가 있는 후보군 제거

우선 1000~9999 중에서 숫자가 중복으로 들어가는 경우를 제거해준다.
문자열을 set 자료형으로 바꾸게되면, 중복되는 문자가 제거된 상태로 남는다. (ex. “3444” : {“3”, “4”})
이를 이용하여, set의 길이가 4인 경우만 nums에 넣어준다.

```py
nums = []

for i in range(1000, 10000):
	if len(set(str(i))) == 4:
		nums.append(i)

2. 최적의 후보군 선택

각 후보군마다 최악의 수를 찾아야하기 때문에, 예상 후보군(g)를 반복문으로 돌린다.
g를 선택했을 때, 남은 후보군인 c에 대한 결과를 groups에 모은다. (경우의 수 :len(cands)^2)
다 돌면, g에 대한 결과에 따라 남게되는 후보군의 수가 groups에 집계된다.
그럼 집계된 것들 중 가장 최악의 경우 수가 있다. 그 수가 가장 작은 예상 후보군(g)을 반환한다.

    def pick(cands):                           

        best_worst = len(cands) + 1
        best_num = cands[0]

        for g in cands: # 예상 후보군

            groups = defaultdict(int) # 다른 후보군과의 관계가 집계되는 곳

            for c in cands:
                key = compare(g, c)
                groups[key] += 1

            worst = max(groups.values()) # 집계된 것 중에서 가장 최악의 수 선택

            if worst < best_worst: # 그 최악의 수가 가장 작은 예상 후보군을 선택
                best_worst = worst
                best_num = g

        return best_num # 최적 후보군 반환

3. pick을 반복하여 결과 필터링

pick을 통해서 최적의 후보군을 선택한다.
하지만 후보군이 많을수록 시간이 오래 걸리기 때문에, 1차적으로 후보군을 줄인다.(first)
처음에 시도할 후보가 있으면, 해당 숫자를 target으로 하여 submit을 한다.
그 결과와 다른 숫자와compare한 결과가 같은 숫자들만 next_nums에 남긴다.

    first = [1234] # 임의의 1차 필터링
    
    while not len(nums) == 1:
        if first:
            target = first.pop()
        else:
            target = pick(nums) # 최적 후보군 선택 (1차 필터링이 다 없어진 후)
        
        r_s, r_b = check(target) # submit이 반환한 문자열을 정수로 바꿔서 반환해주는 함수

        next_nums = []

        for n in nums:
            c_s, c_b = compare(target, n)

            if r_s == c_s and r_b == c_b:
                next_nums.append(n)

        nums = next_nums.copy()

위와 같은 과정을 거치면 6회 이하로 숫자 야구를 클리어할 수 있다.

from collections import defaultdict

def compare(a, b):

    a, b = str(a), str(b)

    s_cnt = 0
    b_cnt = 0

    for i in range(4):
        if a[i] == b[i]:
            s_cnt += 1
            b_cnt -= 1

        b_cnt += b.count(a[i])

    return s_cnt, b_cnt


def solution(n, submit):

    nums = []

    for i in range(1000, 10000):
        if len(set(str(i))) == 4:
            nums.append(i)

    def check(num):
        result = submit(num)

        return int(result[0]), int(result[3])

    def pick(cands):                           

        best_worst = len(cands) + 1
        best_num = cands[0]

        for g in cands:

            groups = defaultdict(int)

            for c in cands:
                key = compare(g, c)
                groups[key] += 1

            worst = max(groups.values())

            if worst < best_worst:
                best_worst = worst
                best_num = g

        return best_num

    first = [1234]
    
    while not len(nums) == 1:
        if first:
            target = first.pop()
        else:
            target = pick(nums)
        
        r_s, r_b = check(target)

        next_nums = []

        for n in nums:
            c_s, c_b = compare(target, n)

            if r_s == c_s and r_b == c_b:
                next_nums.append(n)

        nums = next_nums

    return nums[0]

AI’s comment

좋은 점

1 ) Minimax(최소최대) 로 “가장 나쁜 경우에 남는 후보 수”를 최소화하는 질문을 고르는 접근이 문제에 정확히 맞다. 무작위/그리디가 아니라 최악을 보장하는 선택이라 6회 이하 클리어의 근거가 명확하다.
2 ) 첫 수를 1234로 고정한 first 최적화가 현실적이다. 4536개(=9·9·8·7) 전체에서 pick을 처음부터 돌리면 4536² ≈ 2000만 번의 compare가 필요한데, 첫 수를 박아 이걸 통째로 건너뛰었다. 어차피 정보 없는 첫 질문은 무엇이든 대칭이라 손해도 없다.
3 ) compare가 부수효과 없는 순수 함수라 실제 제출 필터링과 pick 시뮬레이션 양쪽에서 그대로 재사용된다. “각 자리 수가 다름” 제약을 이용해 b.count(a[i])가 0/1이 됨을 활용한 볼 계산도 깔끔하다.

아쉬운 점

1 ) (핵심/관점) pick이 질문 후보를 남은 후보군(cands) 안에서만 고른다(consistent guess only). 이 문제 제약에선 6회로 충분하지만, 이론적으로는 “후보가 아닌 수”를 질문해야 후보가 더 잘게 쪼개지는 경우가 있어 항상 최적은 아니다. 지금 답에 문제는 없고, 최적성을 더 짜내려면 질문 대상을 전체 nums로 확장하는 선택지가 있다는 관점만 남겨둔다.

2 ) (가독성/견고성) 반복 조건이 이중 부정이라 읽기 불편하다. 또 만에 하나 후보가 0이 되면 이 조건은 영영 참이라 무한 루프에 빠진다.

while not len(nums) == 1:   # 수정 전
while len(nums) > 1:        # 수정 후

3 ) (사소/견고성) check가 고정 인덱스 result[0], result[3]에 의존한다. "xS yB" 포맷이 항상 한 자리라 지금은 맞지만, 의도가 드러나는 파싱이 더 안전하다.

return int(result[0]), int(result[3])       # 수정 전
s, b = result.split()                        # 수정 후
return int(s[:-1]), int(b[:-1])

다른 풀이

1 ) compare를 집합 연산으로 간결화
반복문으로 스트라이크/볼을 세는 대신, 겹치는 숫자 수를 집합 교집합으로 구한다. (각 자리 수가 다르다는 제약 덕분에 성립)

def compare(a, b):
    a, b = str(a), str(b)
    strike = sum(x == y for x, y in zip(a, b))   # 원본 반복문의 s_cnt
    ball = len(set(a) & set(b)) - strike          # 공통 숫자 수 - 스트라이크 = 볼
    return strike, ball

2 ) 후보 생성을 permutations로
range(1000, 10000)를 9000번 돌며 set 길이를 검사하는 대신, 서로 다른 4자리 순열을 바로 만든다. (선두 0만 제외)

from itertools import permutations

nums = [int(''.join(p)) for p in permutations('0123456789', 4) if p[0] != '0']  # range+set 필터 대체